import javax.print.attribute.HashPrintRequestAttributeSet;

/**
 * @ClassName KP15_reverseList
 * @Description: TODO
 * @Author: JCC
 * @CreateTime: 2023/10/12 13:55
 */
public class KP15_reverseList {

    /**
     * 单链表
     */
    static class Node {
        public int value;
        public Node next;
        public Node(int value) {
            this.value = value;
        }
    }

    /**
     * 单链表反转 三指针
     * @param head
     * @return
     */
    public static Node reverseLinkList(Node head) {
        Node pre = null;
        while (head != null) {
            Node next = head.next;
            head.next = pre;
            pre = head;
            head = next;
        }
        return pre;
    }

    /**
     * 单链表反转 头插法
     * @param head
     * @return
     */
    public static Node reverseLinkListInsertHead(Node head) {
        Node newHead = new Node(-1);
        while (head != null) {
            Node next = head.next;
            head.next = newHead.next;
            newHead.next = head;
            head = next;
        }
        return newHead.next;
    }

    /**
     * 双链表
     */
    static class DoubleNode {
        public int value;
        public DoubleNode prev;
        public DoubleNode next;
        public DoubleNode(int value) {
            this.value = value;
        }
    }

    /**
     * 双链表反转 头插法
     * @param head
     * @return
     */
    public static DoubleNode reverseLinkListInsertHead(DoubleNode head) {
        DoubleNode newHead = new DoubleNode(-1);
        while (head != null) {
            DoubleNode next = head.next;
            head.next = newHead.next;
            head.prev = next;
            newHead.next = head;
            head = next;
        }
        return newHead.next;
    }


}
